package cn.jdemo.algorithm.dynamicProgramming;

import java.util.LinkedList;

/**
 * 给你一个 只包含正整数 的 非空 数组 nums 。
 * 请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 *
 * 动规5步
 * 1.定义
 *      dp[i] 背包总容量是i，最大可以凑成i的子集总和为dp[i]。
 * 2.递推公式
 *      dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
 * 3.初始化
 *      dp[0] = 0;
 *      dp[1] = max(dp[0]+nums[1],dp[0])
 * 4.遍历顺序
 * 5.示例:nums = [1,5,11,5]
 *      dp[i][11]
 *    0       1
 *    1       6
 *    2       11
 *    4       11
 *
 */
public class CanPartition {
    public static void main(String[] args) {
        int[] nums = new int[]{1,5,11,5};
        boolean res = new CanPartition().canPartition(nums);
        System.out.println(res);
    }
    public boolean canPartition(int[] nums) {
        int length = nums.length;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum+=nums[i];
        }
        if(sum % 2 !=0){
            return false;
        }
        int target = sum/2;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 那么背包内总和不会大于20000，所以定义一个20000大的数组。
        int[] dp = new int[2001];
        for(int i = 0; i < length; i++) {
            for(int j = target; j >= nums[i]; j--) {
                // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target){
            return true;
        }
        return false;
    }
}
